﻿// 890. 能被整除的数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
/*
https://www.acwing.com/problem/content/892/
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式
第一行包含整数 n 和 m。
第二行包含 m 个质数。

输出格式
输出一个整数，表示满足条件的整数的个数。

数据范围
1≤m≤16,
1≤n,pi≤109
输入样例:
10 2
2 3
输出样例：
7
*/

int n, m;
int p[20];
long long ans = 0;
void dfs(int idx,int cnt,long long v) {
	if (idx >= m) return;
	if (v > n) return;
	//选取当前元素
	long long tmp = v * p[idx];
	cnt++;
	if (tmp <= n && cnt %2==1) {
		ans += n / tmp;
		dfs(idx + 1, cnt, tmp);
	}
	else if (tmp <= n && cnt % 2 == 0) {
		ans -= n / tmp;
		dfs(idx + 1, cnt, tmp);
	}
	cnt--;

	//不选取当前元素
	dfs(idx + 1, cnt, v);
	
	return;
}



int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> p[i];
	}

	dfs(0,0,1);

	cout << ans << endl;

	return 0;
}

 